package nowCoder;

/**
 * 输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。
 * 如果是则输出Yes,否则输出No。假设输入的数组的任意两个数字都互不相同。 
 * @author Ghost
 *
 */
public class VerifySquenceOfBST {
	private boolean verify(int[] sequence, int begin, int end){
		if(begin>end)
			return true;
		int root = sequence[end];
		int i=end-1;
		for(;i>=begin && sequence[i]>root;i--);
		int j=i;
		for(;j>=begin && sequence[j]<root;j--);
		if(j>=begin)
			return false;
		else{
			return verify(sequence, begin, j) && verify(sequence, i+1, end-1);
		}
	}
	public boolean VerifySquenceOfBST(int [] sequence) {
		if (sequence==null || sequence.length==0) {
			return false;
		}
		return verify(sequence, 0, sequence.length-1);
    }
	public static void main(String[] args){
		VerifySquenceOfBST verifySquenceOfBST = new VerifySquenceOfBST();
		int[] arr = {};
		System.out.println(verifySquenceOfBST.VerifySquenceOfBST(arr));
	}
}
